#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n=0;
        cin>>n;
        ll ans = n;
        for(int i=2;i<=n/i;i++)
        {
            if(n%i==0) ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
        if(n>1) ans=ans/n*(n-1);
        cout<<ans<<endl;
    }

    return 0;
}
